The Discrete Fourier Transform

When the sequence x[n] is finite---~~say it is defined for only N points, #math236#0≤n≤N - 1---~~then N samples of the Fourier transform, uniformly distributed through the period, give enough information to reconstruct the original signal. This new sequence of samples is called the discrete Fourier transform (DFT). Thus the / DFT X[k] of the N-point sequence x[n] is given by

#math237#

X[k] = #tex2html_wrap_indisplay3232#x[n]e-j2πkn/N,

and the inverse transformation is

#math238#

x[n] = #tex2html_wrap_indisplay3234##tex2html_wrap_indisplay3235#X[k]ej2πkn/N.

The symbolic DFT can be implemented either by this formula, or as the DTFT of x[n] over the range #math239#n = 0, 1,…, N - 1, followed by sampling at the points #math240#wk = 2πk/N, for #math241#k = 0, 1,…, N - 1.

Since the DFT is discrete in both the time and frequency domains, it can be computed and stored numerically, as well as symbolically. The <#505#>Fourier<#505#> function provided with the 1.2 release of / implements the numerical DFT, whereas the 79 function 80 implements a symbolic DFT. Given a sequence, this function first takes its DTFT, then factors the result, if possible, into the product of a real-valued amplitude and a phase function. For example:

<#3240#> 
verbatim185#
<#3240#>
The phase function here is the exponential, and the amplitude function a ratio of two sinusoids. In fact, the amplitude is none other than the aliased sinc function introduced in Table 1. In discrete time, this function is the DTFT of an N-point rectangular window.

Like the forward DFT, the inverse DFT rule base relies on a DTFT rule base. <#513#>InvDFTransform<#513#> operates on finite-extent sequences and requires three arguments: X[k], N, and k. Its only strategy rewrites the sampled frequency response into a continuous one and then calls the inverse DTFT.